package com.dmall.directed.graph;

import java.util.*;

/**
 * 欧拉回路
 * @author xiao1.wang
 * @date 2022-07-05 14:24:41
 */
public class DirectedEulerLoop {

    private Graph G;

    public DirectedEulerLoop(Graph G) {
        if (!G.isDirected()) {
            throw new IllegalArgumentException("DirectedEulerLoop only works in directed graph.");
        }
        this.G = G;
    }

    public boolean hasEulerLoop() {
        /*CC cc = new CC(G);
        if (cc.count() > 1) {
            return false;
        }*/
        for (int v = 0; v < G.V(); v++) {
            if (G.indegree(v) != G.outdegree(v)) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (!hasEulerLoop()) {
            return res;
        }
        Graph g = (Graph) G.clone();
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (g.outdegree(v) > 0) {
                int w = g.adj(v).iterator().next();
                stack.push(w);
                g.removeEdge(v, w);
            } else {
                res.add(v);
                stack.pop();
            }
        }
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        String filename = DirectedEulerLoop.class.getClassLoader().getResource("com/dmall/directed/graph/ug.txt").getPath();
        Graph g = new Graph(filename, true);
        DirectedEulerLoop el = new DirectedEulerLoop(g);
        System.out.println(el.result());

        String filename2 = DirectedEulerLoop.class.getClassLoader().getResource("com/dmall/directed/graph/ug2.txt").getPath();
        Graph g2 = new Graph(filename2, true);
        DirectedEulerLoop el2 = new DirectedEulerLoop(g2);
        System.out.println(el2.result());
    }
}
